/*
664. [奇怪的打印机](https://leetcode.cn/problems/strange-printer/description/)

辛泽豪

 */

code:

class Solution {
public:
    // 主函数，计算打印字符串s所需的最少操作次数
    int strangePrinter(string s) {
        if (s.empty()) return 0;  // 如果字符串为空，不需要任何操作
        
        int dp[110][110];  // 动态规划数组，dp[i][j]表示打印s[i...j]所需的最少操作次数
        int n = s.size();  // 字符串s的长度
        memset(dp, 0x3f, sizeof(dp));  // 初始化dp数组为一个很大的值（无穷大）

        // 遍历所有可能的子串长度len
        for (int len = 1; len <= n; len++) {
            // 遍历所有可能的子串起点i
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;  // 子串终点j
                
                // 如果子串长度为1，只需要一次操作
                if (len == 1) dp[i][j] = 1;
                
                // 如果子串长度大于等于2
                if (len >= 2) {
                    // 如果子串的第一个字符与最后一个字符相同，或者第一个字符与下一个字符相同
                    if (s[i] == s[j] || s[i] == s[i + 1]) {
                        dp[i][j] = dp[i + 1][j];  // 可以通过打印s[i+1...j]然后覆盖第一个字符来完成
                    }
                    // 如果子串的最后一个字符与第一个字符相同，或者最后一个字符与前一个字符相同
                    if (s[j] == s[i] || s[j] == s[j - 1]) {
                        dp[i][j] = dp[i][j - 1];  // 可以通过打印s[i...j-1]然后覆盖最后一个字符来完成
                    }

                    // 枚举子串的分割点k，尝试将子串分为两部分s[i...k]和s[k+1...j]
                    for (int k = i; k < j; k++) {
                        // 更新dp[i][j]为dp[i][k] + dp[k+1][j]的最小值
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        // 返回打印整个字符串s所需的最少操作次数
        return dp[0][n - 1];
    }
};
